package com.wang;

import java.util.Arrays;
import java.util.Random;

/**
 * 快速排序
 * 快排基于分治思想
 * 核心是通过分区操作将数组分为两部分, 再递归对两部分进行排序.
 * 平均时间复杂度为O(nlogn)，最坏情况O(n²)
 * @author yandong
 */
public class QuickSort {
    public void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0) {
            return;
        }

        if (low < high) {
            // 获取基准值
            int pivot = partition(arr, low, high);
            // 递归对左区间进行排序
            quickSort(arr, low, pivot - 1);
            // 递归对右区间进行排序
            quickSort(arr, pivot + 1, high);
        }
    }

    private int partition(int[] arr, int low, int high) {
        // 获取基准值, 基准值是数组第一个元素, 所以要先从后边开始找
        // int pivot = arr[low];
        // 随机选择一个索引作为基准，交换到low位置
        int randomIndex = low + new Random().nextInt(high - low + 1);
        swap(arr, low, randomIndex);

        int pivot = arr[low];

        while (low < high) {

            while (low < high && arr[high] >= pivot) {
                // high位置的元素大于等于pivot, high就继续向左移动
                high--;
            }
            // high位置的元素小于pivot, 则将high位置的元素赋给low位置
            arr[low] = arr[high];

            while (low < high && arr[low] <= pivot) {
                // low位置的元素小于等于pivot, low就继续向右移动
                low++;
            }
            // low位置的元素大于等于pivot, 则将low位置的元素赋给high位置
            arr[high] = arr[low];
        }

        // 循环结束, low和high相等 指向同一位置
        // 此时将pivot赋给low位置
        arr[low] = pivot;
        return low;
    }

    private void swap(int[] arr, int low, int randomIndex) {
        int temp = arr[low];
        arr[low] = arr[randomIndex];
        arr[randomIndex] = temp;
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] arr = new int[]{8, 11, 3, 2, 0, 67, 5, 99, 77};
        quickSort.quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
